package 二叉树;

import java.util.Deque;
import java.util.LinkedList;

public class q117填充每个节点的下一个右侧节点指针II {

    // Definition for a Node.
    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }



    public Node connect(Node root) {
        if(root==null){
            return null;
        }
        Deque<Node> que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()){
            int size = que.size();
            Node tmp = que.poll();
            if(tmp.left!=null) que.offer(tmp.left);
            if(tmp.right!=null) que.offer(tmp.right);
            for(int i = 1 ; i < size ; i++){
                Node node = que.poll();
                tmp.next = node;
                tmp = node;
                if(node.left!=null) que.offer(node.left);
                if(node.right!=null) que.offer(node.right);
            }

        }
        return root;
    }
}

// Definition for a Node.


